package com.example.question.tree.tree2;

import com.example.question.tree.tree1.Tree;
import com.example.question.tree.tree1.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Code06_AllPath {
    public static void main(String[] args) {
        TreeNode node = Tree.createTree(new Integer[]{1, 2, 3, null, null, 4, null, null, 5, null, 6, null, null});
        Code06_AllPath path = new Code06_AllPath();
        System.out.println("path.path(node) = " + path.path(node));
    }

    // 这个是经典的递归回溯
    public List<List<Integer>> path(TreeNode node) {
        List<List<Integer>> ret = new ArrayList<>();
        dfs(node, ret, new ArrayList<>());
        return ret;
    }

    private void dfs(TreeNode node, List<List<Integer>> ret, List<Integer> path) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        if (node.left == null && node.right == null) {
//            path.add(node.val);
            //  不能指向同一个
            ret.add(new ArrayList<>(path));
        }
        dfs(node.left, ret, path);
        dfs(node.right, ret, path);
        // 回溯的过程中，将当前节点从path中删除
        path.remove(path.size() - 1);
    }
}
